package interview;

import java.util.Objects;

/**
 * ### 问题 1：什么是`git rebase` ？你在哪些情况下会使用它？
 * <p>
 * `Git rebase` 是一种将一个分支的修改合并到另一个分支上的方法。它可以用于将一个分支的修改合并到主分支上，从而更好地保持主分支的整洁和一致性。它也可以用于将多个分支的修改合并到一个分支上，以避免合并冲突并维护一个干净的提交历史。此外，当需要更新提交历史或重新组织提交时，也可以使用 `git rebase`。
 * <p>
 * 一些使用 `git rebase` 的情况包括：将多个分支合并到单个分支、更新提交历史、保持主分支干净和一致、以及在团队合作时协调不同分支的工作。
 * <p>
 * ### 问题 2：实现`git rebase`核心算法
 * <p>
 * ###
 * <p>
 * 假设你正在开发一个版本控制系统，其中的版本历史被组织成一个二叉树。每个节点表示一个提交，每个提交都有一个唯一的哈希值和一个父节点。
 * <p>
 * `git rebase` 的核心算法是将一个分支的修改应用到另一个分支上。具体来说，它通过以下步骤实现：
 * <p>
 * 1. 找到两个分支的最小公共祖先。
 * 2. 在当前分支上创建一个新的提交，该提交包含来自要合并的分支的修改。
 * 3. 将当前分支指向新创建的提交。
 * 4. 将原始提交应用到新提交上。
 */
public class GitRebase {

    public CommitNode findLowestCommonAncestor(CommitNode root, CommitNode p1, CommitNode p2) {
        // 两个提交的最小公共祖先
        if (root == null) {
            return null;
        }
        CommitNode left = findLowestCommonAncestor(root.left, p1, p2);
        CommitNode right = findLowestCommonAncestor(root.right, p1, p2);
        if (Objects.equals(root, p1) || Objects.equals(root, p2) || left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    public static class CommitNode {

        private String commitHash;
        private CommitNode left;
        private CommitNode right;
        // 省略 getter setter


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CommitNode that = (CommitNode) o;
            return Objects.equals(commitHash, that.commitHash);
        }

    }

}